import utils.TreeNode;

/**
 * @Author ZhangCuirong
 * @Date 2025/8/5 12:14
 * @description:
 */
public class Solution124 {
    private int maxSum = Integer.MIN_VALUE; // 全局最大路径和

    public int maxPathSum(TreeNode root) {
        maxSum = Integer.MIN_VALUE;
        singleMaxSum(root); // 递归计算单边路径和，同时更新maxSum
        return maxSum;
    }

    /**
     * 计算从当前节点出发的单边最大路径和（只能向左或向右延伸）
     * 同时更新全局最大路径和（以当前节点为根，包含左右子树的路径）
     */
    private int singleMaxSum(TreeNode root) {
        if (root == null) {
            return 0; // 空节点贡献0
        }

        // 递归计算左右子树的单边路径和（负数则取0，即舍弃该子树）
        int left = Math.max(0, singleMaxSum(root.left));
        int right = Math.max(0, singleMaxSum(root.right));

        // 以当前节点为根的路径和 = 当前节点值 + 左单边和 + 右单边和
        int currentPathSum = root.val + left + right;
        // 更新全局最大路径和
        maxSum = Math.max(maxSum, currentPathSum);

        // 返回单边最大路径和（当前节点值 + 左右子树中较大的单边和）
        return root.val + Math.max(left, right);
    }

    public static void main(String[] args) {
        Solution124 solution = new Solution124();
//        int[] nums = {-10, 9, 20, -1, -1, 15, 7};
        int[] nums = {-2,-3};
        TreeNode root = TreeNode.buildTree(nums);
        int res = solution.maxPathSum(root);
        System.out.println(res);
    }
}
